class Solution
{
public:
    int nthUglyNumber(int n)
    {
        priority_queue<long long, vector<long long>, greater<long long>> heap;
        unordered_set<long long> visited{1};
        heap.push(1);
        auto seeAndPush = [&](long long num)
        {
            if (!visited.count(num))
            {
                heap.push(num);
                visited.insert(num);
            }
        };
        int i = 0;
        while (true)
        {
            long long uglyNum = heap.top();
            heap.pop();
            ++i;
            if (i == n)
            {
                return uglyNum;
            }
            seeAndPush(uglyNum * 2);
            seeAndPush(uglyNum * 3);
            seeAndPush(uglyNum * 5);
        }
        return 1;
    }
};